package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Administrator
 * @date 2019/12/2 17:32
 */
public class Decoding {
    /**
     * 一条包含字母 A-Z 的消息通过以下方式进行了编码：
     * 'A' -> 1
     * 'B' -> 2
     * ...
     * 'Z' -> 26
     * 给定一个只包含数字的非空字符串，请计算解码方法的总数。
     */
    @Test
    public void numDecoding() {
        Assert.assertEquals(1, numDecoding("27"));
        Assert.assertEquals(21, numDecoding("1222222"));
        Assert.assertEquals(1, numDecoding2("27"));
        Assert.assertEquals(21, numDecoding2("1222222"));
    }

    public int numDecoding(String s) {
        if (s.charAt(0) == '0') {
            return 0;
        }
        char[] chars = s.toCharArray();
        int[] dp = new int[chars.length + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == '0') {
                if (chars[i - 1] == '1' || chars[i - 1] == '2') {
                    dp[i + 1] = dp[i - 1];
                } else {
                    return 0;
                }
            } else {
                if (chars[i - 1] == '1' || (chars[i - 1] == '2' && chars[i] < '7' && chars[i] > '0')) {
                    dp[i + 1] = dp[i - 1] + dp[i];
                } else {
                    dp[i + 1] = dp[i];
                }
            }
        }
        return dp[chars.length];
    }

    public int numDecoding2(String s) {
        if (s.charAt(0) == '0') return 0;
        char[] chars = s.toCharArray();
        int pre = 1, cur = 1;
        for (int i = 1; i < chars.length; i++) {
            int tmp = cur;
            if (chars[i] == '0') {
                if (chars[i - 1] == '1' || chars[i - 1] == '2')
                    cur = pre;
                else
                    return 0;
            } else {
                if (chars[i - 1] == '1' || (chars[i - 1] == '2' && chars[i] < '7' && chars[i] > '0'))
                    cur = cur + pre;
            }
            pre = tmp;
        }
        return cur;
    }

    /**
     * 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
     */
    @Test
    public void longestValidParentheses() {
        Assert.assertEquals(0, longestValidParentheses(""));
        Assert.assertEquals(0, longestValidParentheses(")"));
        Assert.assertEquals(2, longestValidParentheses("(()"));
        Assert.assertEquals(2, longestValidParentheses("())"));
        Assert.assertEquals(4, longestValidParentheses(")()())"));
        Assert.assertEquals(6, longestValidParentheses("((()))"));
        Assert.assertEquals(6, longestValidParentheses("()(((()))"));
        Assert.assertEquals(8, longestValidParentheses("()((()))"));
    }

    public int longestValidParentheses(String s) {
        int max = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }


    /**
     * 删除无效的括号
     * 删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
     * 说明: 输入可能包含了除 ( 和 ) 以外的字符。
     */
    @Test
    public void removeInvalidParentheses() {
        Assert.assertArrayEquals(new String[]{"(())()", "()()()"}, removeInvalidParentheses("()())()").toArray(new String[0]));
        Assert.assertArrayEquals(new String[]{"(a())()", "(a)()()"}, removeInvalidParentheses("(a)())()").toArray(new String[0]));
        Assert.assertArrayEquals(new String[]{""}, removeInvalidParentheses(")(").toArray(new String[0]));
        Assert.assertArrayEquals(new String[]{""}, removeInvalidParentheses("(").toArray(new String[0]));
        Assert.assertArrayEquals(new String[]{""}, removeInvalidParentheses("))").toArray(new String[0]));
        Assert.assertArrayEquals(new String[]{"()"}, removeInvalidParentheses("(()").toArray(new String[0]));
        Assert.assertArrayEquals(new String[]{""}, removeInvalidParentheses("(((").toArray(new String[0]));
    }

    public List<String> removeInvalidParentheses(String s) {
        final int n = s.length();
        int lDel = 0, rDel = 0;
        final char[] cs = s.toCharArray();
        for (char c : cs) {
            if (c == '(') {
                lDel++;
            } else if (c == ')') {
                if (lDel == 0) {
                    rDel++;
                } else lDel--;
            }
        }
        List<String> res = new ArrayList<>();
        removeInvalidParentheses(res, new StringBuilder(n - lDel - rDel), cs, 0, 0, 0, lDel, rDel);
        return res;
    }

    private void removeInvalidParentheses(List<String> res, StringBuilder sb,
                                          char[] cs, int cur,
                                          int lCnt, int rCnt, int lDel, int rDel) {
        final int n = cs.length;
        if (cur == n) {
            if (lDel == 0 && rDel == 0) {
                res.add(sb.toString());
            }
            return;
        }
        final int len = sb.length();
        if (cs[cur] == '(') {
            // not use
            if (lDel > 0) {
                int next = cur + 1;
                while (next < n && cs[next] == '(') next++; //
                removeInvalidParentheses(res, sb, cs, next, lCnt, rCnt, lDel - next + cur, rDel);
            }
            // use
            sb.append('(');
            removeInvalidParentheses(res, sb, cs, cur + 1, lCnt + 1, rCnt, lDel, rDel);
        } else if (cs[cur] == ')') {
            // not use
            if (rDel > 0) {
                int next = cur + 1;
                while (next < n && cs[next] == ')') next++; //
                removeInvalidParentheses(res, sb, cs, next, lCnt, rCnt, lDel, rDel - next + cur);
            }
            // use
            if (rCnt < lCnt) {
                sb.append(')');
                removeInvalidParentheses(res, sb, cs, cur + 1, lCnt, rCnt + 1, lDel, rDel);
            }
        } else {
            sb.append(cs[cur]);
            removeInvalidParentheses(res, sb, cs, cur + 1, lCnt, rCnt, lDel, rDel);
        }
        sb.setLength(len);
    }

}
